The Internet, as it has grown considerably in size and popularity, is being used to provide various services and applications to users. Diverse applications, such as streaming a short movie demonstrating how to assemble a piece of furniture, taking a virtual tour of a real estate property or a scenic spot, watching a live performance of an artist, and participating in a networked multi-user computer game or conference, are all available to users via the Internet.
An important trend is that users are no longer satisfied with receiving services that are targeted at mass audiences. Users are demanding services that are tailored to their individual needs. With the proliferation of personalized services, an important challenge facing future network infrastructure is balancing the tradeoffs between providing individualized services to each user and making efficient use of network resources.
A fundamental challenge in effectively utilizing network resources and services is efficiently and quickly locating desired resources/services in large networks, such as the Internet. For example, a user may generate a query for finding particular media content available in the network. Location and distance estimation techniques may be used to find the closest cache or proxy in the network that provides the desired data or service, such as the desired media content.
Landmark clustering is a known location and distance estimation technique for determining a distance to a node in a network. Landmark clustering was introduced for routing in large networks. A node's physical location in a network is estimated by determining the node's distance to a common set of landmark nodes in the network. Landmark clustering assumes that if two nodes have similar distances (e.g., measured latencies) to the landmark nodes, the two nodes are likely to be close to each other. Routers store the estimated physical locations of the nodes and use the position information for routing to the closest node.
FIG. 8 illustrates estimating physical locations for the nodes 810 and 820 in the network 800 using landmark clustering. The client nodes 810 and 820 determine their distances to the landmark nodes L801 and L802. Because the nodes 810 and 820 have similar distances to the landmark nodes L801 and L802, the nodes 810 and 820 are determined to be close to each other.
Landmark clustering is an efficient technique for determining general locations for nodes in a network. However, current landmark clustering techniques tend to result in false clustering, where nodes that are far away in network distance are clustered near each other. That is nodes that are far away from landmark nodes tend be estimated as having locations near each other when in fact they are located at substantial distances from each other. Secondly, landmark clustering is a coarse-grained approximation and is not effective in differentiating between nodes that are relatively close in distance.